package DynamicProgramming;

import java.util.ArrayList;
import java.util.List;

public class _638_ShoppingOffers {
    public int shoppingOffers(List < Integer > price, List < List < Integer >> special, List < Integer > needs) {
        return shopping(price, special, needs);
    }
    public int shopping(List < Integer > price, List < List < Integer >> special, List < Integer > needs) {
        int j = 0, res = getSum(needs, price);
        for (List < Integer > s: special) {
            List < Integer > clone = new ArrayList<>(needs);
            for (j = 0; j < needs.size(); j++) {
                int diff = clone.get(j) - s.get(j);
                if (diff < 0)
                    break;
                clone.set(j, diff);
            }
            if (j == needs.size())
                res = Math.min(res, s.get(j) + shopping(price, special, clone));
        }
        return res;
    }
    public int getSum(List < Integer > counts, List < Integer > price) {
        int sum = 0;
        for (int i = 0; i < counts.size(); i++) {
            sum += counts.get(i) * price.get(i);
        }
        return sum;
    }

}
